A word $w$ is called synchronizing (recurrent, reset, magic, directable) wordof deterministic finite automaton (DFA) if $w$ sends all states of theautomaton to a unique state. In 1964 Jan \v{C}erny found a sequence of n-statecomplete DFA possessing a minimal synchronizing word of length $(n-1)^2$. Heconjectured that it is an upper bound on the length of such words for completeDFA. Nevertheless, the best upper bound $(n^3-n)/6$ was found almost 30 yearsago. We reduce the upper bound on the length of the minimal synchronizing wordto $n(7n^2+6n-16)/48$. An implemented algorithm for finding synchronizing wordwith restricted upper bound is described. The work presents the distribution ofall synchronizing automata of small size according to the length of an almostminimal synchronizing word.
展开▼
机译：如果$ w $将自动机的所有状态发送到唯一状态，则将单词$ w $称为确定性有限自动机（DFA）的同步（循环，重置，魔术，可定向）字。 1964年1月\ v {C} erny发现了n个状态完全DFA序列，该序列具有最小同步字，长度为$（n-1）^ 2 $。他推测，对于completeDFA，这是单词长度的上限。然而，最好的上限$（n ^ 3-n）/ 6 $被发现接近30年。我们将最小同步字长度的上限减小为$ n（7n ^ 2 + 6n-16）/ 48 $。描述了一种用于找到具有受限上限的同步词的实现算法。这项工作根据几乎最小的同步字的长度提出了所有小尺寸的同步自动机的分布。
展开▼
